/**
 * @file     searchInsertPosition.js
 * @brief    [35. 搜索插入位置](https://leetcode.cn/problems/search-insert-position/)
 * @author   Zhu
 * @date     2024-11-27 11:24
 */

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function (nums, target) {
    const n = nums.length;
    // i  ... mid ...  j ans
    let i = 0,
        j = n - 1,
        ans = n;
    while (i <= j) {
        const mid = (i + j) >> 1; // floor
        if (target <= nums[mid]) {
            ans = mid;
            j = mid - 1;
        } else i = mid + 1;
    }

    return ans;
};

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function (nums, target) {
    let low = 0;
    let high = nums.length - 1;
    let mid = Math.floor((high + low) / 2);

    while (low < high) {
        if (target <= nums[mid]) {
            high = mid;
        } else {
            low = mid + 1;
        }
        mid = Math.floor((high + low) / 2);
    }

    if (target > nums[mid]) return low + 1;

    return low;
};
